package com.kk.datastructure.linkedlist.interview;
import java.util.Stack;


/**
 * title: 单链表的面试题
 * @author 阿K
 * 2020年11月22日 下午10:36:50 
 */
public class SingleLinkedListInterview {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		// 先创建节点
		HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
		HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
		HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
		HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
		HeroNode hero5 = new HeroNode(5, "鲁智深", "花和尚");
		HeroNode hero6 = new HeroNode(6, "武松", "行者");

		// 创建要给链表
		SingleLinkedList singleLinkedList = new SingleLinkedList();

//		singleLinkedList.addByOrder(hero1);
//		singleLinkedList.addByOrder(hero4);
//		singleLinkedList.addByOrder(hero2);
//		singleLinkedList.addByOrder(hero3);
		
		singleLinkedList.list();
		
		// 有效个数
		int length = singleLinkedList.getLength(singleLinkedList.getHead());
		System.out.printf("有效个数为：%d\n",length);

		// 倒数第 K 的节点
		HeroNode resultNode = singleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 3);
		System.out.println(resultNode);
		
		// 链表反转
		singleLinkedList.reversetList(singleLinkedList.getHead());
		singleLinkedList.list();
		
		// 利用栈反向打印
		singleLinkedList.reversetPrint(singleLinkedList.getHead());
		
		System.out.println("--------------------美丽的分割线---------------------------");
		
		SingleLinkedList singleLinkedList1 = new SingleLinkedList();
		SingleLinkedList singleLinkedList2 = new SingleLinkedList();
		
		singleLinkedList1.add(hero6);
		singleLinkedList1.add(hero2);
		singleLinkedList1.add(hero4);
		singleLinkedList2.add(hero5);
		singleLinkedList2.add(hero1);
		singleLinkedList2.add(hero3);
		
		singleLinkedList1.list();
		singleLinkedList2.list();
		
		System.out.println("--------------------美丽的分割线---------------------------");

		HeroNode newHead = singleLinkedList.sumLinkedList(singleLinkedList1.getHead(),
				singleLinkedList2.getHead());
		
		SingleLinkedList singleLinkedList3 = new SingleLinkedList();
		singleLinkedList3.setHead(newHead);
		singleLinkedList3.list();
		
		
	}

}

//定义 SingleLinkedList 管理梁山英雄
class SingleLinkedList {
	// 先初始化一个头节点,头节点不能动,不存放具体的数据（可以理解为王伦 -- 初代寨主，后被林冲捅了）
	private HeroNode head = new HeroNode(0, null, null);

	// 返回头结点
	public HeroNode getHead() {
		return head;
	}
	
	public void setHead(HeroNode head) {
		this.head = head;
	}
	
	
	/**
	 * 题目五：合并两个有序的单链表，合并之后的链表依然有序
	 * @param head1
	 * @param head2
	 * 想了很久，有两个解法：只实现方案一
	 * 方案一：遍历A 链表找出最小的号，再遍历B链表找出最小，然后比较
	 * 小的先插入到新链表中，依次重复(每一次最小的，要被摘除)--有问题未解决
	 * 方案二：就是模仿数组的冒泡排序，左右比较交换，未实现
	 * 方案三：调用addByOrder()循环插入，直到等于有效长度--失败
	 * 方案四：找出最小然后添加进去新链表中，在旧链表中摘除已经添加的，循环直到新链表满足旧链表其实长度
	 * @return
	 */
	public static HeroNode sumLinkedList(HeroNode head1,HeroNode head2) {
		// 方案三：
		// 判空 
		if (head1.next == null || head2.next == null)
			return null;
		// 定义一个新链表用于存储合并后的有序
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		// 合并后未排序
		SingleLinkedList originalLinkedList = new SingleLinkedList();
		
		// 先合并再排序 
		// 合并 head1链表最后一个接 head2的后米面一个
//		HeroNode cuc1 = head1.next; 
//		// 中间层 绑定head1 和 head2
//		HeroNode temp = null;
//		while (cuc1 != null) {
//			temp = cuc1;
//			cuc1 = cuc1.next;
//		}
//		
//		// 合并
//		temp.next = head2.next;
//		cuc1 = temp;
//		originalLinkedList.setHead(head1);
		
		HeroNode cuc1 = head1.next;
		HeroNode cuc2 = head2.next;
		while(cuc1!=null) {
			originalLinkedList.add(cuc1);
			cuc1 = cuc1.next;
		}
		while(cuc2!=null) {
			originalLinkedList.add(cuc2);
			cuc2 = cuc2.next;
		}
		
		// 开始循环插入 直到等于有效个数
		int resultNum = singleLinkedList.getLength(head1);
		int count = 0;// 每次插入后的变化值
		HeroNode minNode = null; // 节点最小序号
	
		// 开始插入
		while(count<resultNum) {		
			// 得到最小
			HeroNode tempC = originalLinkedList.getHead().next;
			while(tempC.next!=null) {
				// 初始化
				minNode = tempC;
				if(tempC.no>tempC.next.no) {
					minNode = tempC.next;
				}
				tempC = tempC.next;
			}
			singleLinkedList.addByOrder(minNode);
			// 摘除
			originalLinkedList.delete(minNode.no,originalLinkedList);
			
			count = singleLinkedList.getLength(singleLinkedList.getHead());
		}
		
		return singleLinkedList.getHead();
				  
		
		//方案一：作废
		/*
		 * // 判空 if(head1.next ==null || head2.next == null)return null; // 定义一个新链表
		 * 用于存储合并 //SingleLinkedList singleLinkedList = new SingleLinkedList(); //
		 * 定义一个新链表的头 HeroNode newHead = new HeroNode(0, "", ""); // 先合并再排序 // 合并 head1
		 * 链表最后一个接 head2的后米面一个 HeroNode cuc1 = head1.next; HeroNode temp = null;
		 * while(cuc1!=null) { // 最后一个为null 将他前一个先保存 temp = cuc1; cuc1 = cuc1.next; } //
		 * head2 绑定head1 的后面一个 temp.next = head2.next;
		 * 
		 * // 现在已经输合并的无序链表 head1 // 遍历得到最小 HeroNode minNode = null; // 最小的前一个，用于摘除原始最小
		 * HeroNode minNodeFront = null; // 辅助遍历最小 HeroNode minTemp1 = head1.next; // 填充
		 * 次数为 链表长度 int lengt1 = SingleLinkedList.getLength(newHead); int lengt2 =
		 * SingleLinkedList.getLength(head1);
		 * while(SingleLinkedList.getLength(newHead)<=lengt2) { while(minTemp1.next !=
		 * null) { minNode = minTemp1; // 临时保存 用于摘除它后面的 //HeroNode minTemp2 = minTemp1;
		 * if(minNode.no > minNode.next.no) { // 赋值 minNodeFront = minTemp1; minNode =
		 * minNode.next;
		 * 
		 * } // 后移 minTemp1 = minTemp1.next; } // 摘除最小 minNodeFront.next =
		 * minNodeFront.next.next; // 绑定到 新链表 minNode.next = newHead.next; newHead.next
		 * = minNode; }
		 * 
		 * return newHead;
		 */
	}
	
	public void delete(int no) {
		HeroNode temp = head;
		boolean flag = false;// 标志是否找到待删除节点
		while(true) {
			if(temp.next ==null)
				// 已经到链表的最后
				break;
			if(temp.next.no == no) {
				// 已经找到
				flag = true;
				break;
			}
			// 移动继续找
			temp = temp.next;
		}
		// 通过 flag 进行判断
		if(flag) {
			// 已经找到，指向后一个引用
			temp.next = temp.next.next;
		}else 
			System.out.printf("没有找到排行为【%d】要删除的英雄",no);		
	}
	public void delete(int no,SingleLinkedList singleLinkedList) {
		HeroNode temp = null;
	
		 temp = singleLinkedList.getHead();
		boolean flag = false;// 标志是否找到待删除节点
		while(true) {
			if(temp.next ==null)
				// 已经到链表的最后
				break;
			if(temp.next.no == no) {
				// 已经找到
				flag = true;
				break;
			}
			// 移动继续找
			temp = temp.next;
		}
		// 通过 flag 进行判断
		if(flag) {
			// 已经找到，指向后一个引用
			temp.next = temp.next.next;
		}else 
			System.out.printf("没有找到排行为【%d】要删除的英雄",no);		
	}
	
	/**
	 * 题目四：反向打印链表(栈)
	 * @param head
	 */
	public static void reversetPrint(HeroNode head) {
		// 判空
		if(head.next == null)return;
		
		// 创建一个栈，用于节点出入栈，实现反向打印
		Stack<HeroNode> stack = new Stack();
		// 定义辅助指针，用于遍历原始链表
		HeroNode cuc = head.next;
		// 将链表所有节点入栈
		while (cuc != null) {
			stack.push(cuc);// 节点 入栈
			cuc = cuc.next;// 节点后移
		}
		// 所有节点依次出栈
		while( stack.size() >0) {
			//stack的特点是先进后出
			System.out.println(stack.pop());
		}
	}

	/**
	 * 题目三：单链表的反转【腾讯面试题，有点难度】
	 * 
	 * @param head
	 */
	public static void reversetList(HeroNode head) {
		// 若链表为空，或者只有一个则不需要反转
		if (head.next == null || head.next.next == null) {
			return;
		}
		// 定义一个辅助指针，用户遍历原始未反转的那个链表
		HeroNode cuc = head.next;
		// 用于动态指向 当前节点【cuc】的 下一个节点
		HeroNode next = null;
		// 新链表(反转后的)的链表头
		HeroNode reversetHead = new HeroNode(0, "", "");
		// 思路： 遍历原始链表，没遍历一个节点将其取出，并放在新链表头(reversetHead)的后面的最前端
		// 每一个新节点，都会取代旧的，与新链表头牵手
		while (cuc != null) {
			// 暂时先保存当前节点的下一个节点，用于后移
			next = cuc.next;
			// 将要 遍历出来的新节点，指向 新链表头 后面的最前端(将情敌的手，从她手上拨开)
			cuc.next = reversetHead.next;
			// 将 cuc 连接到 新的链表头后面的最前端(她的手和你牵了)
			reversetHead.next = cuc;
			// cuc 后移，换下一个情敌来打你
			cuc = next;
		}
		// 将head.next 指向 reverseHead.next , 实现单链表的反转
		// 新链表(她)池塘养的鱼和旧链表头(她的闺蜜)共享
		head.next = reversetHead.next;
	}

	/**
	 * 题目二：查找单链表中的倒数第k个结点 【新浪面试题】
	 * 
	 * @param head     传入的头结点
	 * @param HeroNode 需要查找的 倒数节点数据
	 * @return
	 */
	// 思路：
	// 1、先遍历得到 有效数据个数（总长度--不包括头节点）
	// 2、有效个数 - index = 倒数 K(size-index = k )
	// 3、找到则返回当前节点，找不到返回 null
	public static HeroNode findLastIndexNode(HeroNode head, int index) {
		// 判空
		if (head.next == null)
			return null;

		// 第一个遍历得到链表的长度(节点个数)
		int size = getLength(head);

		// 第二次遍历 size-index 位置，就是我们倒数的第K个节点
		// 先做一个index的校验
		if (index <= 0 || index > size) {
			// 查找的位置不能大过总长
			return null;
		}

		// 定义给辅助变量， for 循环定位到倒数的index
		HeroNode cuc = head.next;// 8-2=6,倒数第二个就是第六个
		for (int i = 0; i < size - index; i++) {
			cuc = cuc.next;
		}
		return cuc;
	}

	/**
	 * 题目一：获取有效节点个数
	 * 
	 * @param head 头结点(不统计)
	 * @return 返回有效节点个数
	 */
	public static int getLength(HeroNode head) {
		// 判空
		if (head.next == null)
			return 0;
		int length = 0;
		// 定义辅助变量 cuc,此处没有统计 头节点
		HeroNode cuc = head.next;
		while (cuc != null) {
			length++;
			cuc = cuc.next;// 指向下一个，继续遍历
		}
		return length;
	}

	// 按编号顺序添加（如果有这个排名，则添加失败，并给出提示）
	public void addByOrder(HeroNode heroNode) {
		// 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
		// 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
		HeroNode temp = head;
		boolean flag = false;// flag标志添加的编号是否存在，默认为false
		while (true) {
			if (temp.next == null)
				break;
			if (temp.next.no > heroNode.no)
				// 位置找到，就在 temp后面
				// 因为 它满足了 按顺序 ，所以可以插入
				break;
			if (temp.next.no == heroNode.no) {
				// 已经存在改排行的编号(不可重复)
				flag = true;
				break;
			}
			// 没满足以上，后移下一次节点继续找
			temp = temp.next;
		}

		// 对 flag 进行判断
		if (flag)
			// 不能添加，说明编号已经存在
			System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
		else {
			// 插入到链表中，temp的后面
			heroNode.next = temp.next;// 我后面的是6号，然后我上前走过去，你走了，现在你后面是6号
			temp.next = heroNode;// 我后面是你，上下两句顺序不可对调
		}
	}
	
	 public void add(HeroNode heroNode) {
	        // 因为head节点不能动，因此我们需要一个辅助变量 temp（可以理解为晁天王）
	        HeroNode temp = head;
	        // 遍历链表，找到最后
	        while(true) {
	            // 找到链表的最后是null 
	            if(temp.next == null)break;
	            // 若没有找到最后，则后移(这里是n+1次的，n个有效数据)
	            temp = temp.next;
	        }
	        // 当退出while循环时，temp就指向了链表的最后
	        // 将最后这个节点的next 指向 新的节点
	        temp.next = heroNode;               
	    }

	// 遍历链表
	public void list() {
		// 判断链表是否为空
		if (head.next == null) {
			System.out.println("链表为空~~~");
			return;
		}
		// 因为头节点，不能动，因此我们需要一个辅助变量来遍历
		HeroNode temp = head.next;

		while (true) {
			// 判断是否到链表的最后
			if (temp == null)
				return;

			// 输出节点信息
			System.out.println(temp);
			// 将节点后移，注意要加！！
			temp = temp.next;
		}
	}
}

//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
	public int no; // 好汉排行
	public String name; // 好汉姓名
	public String nickname;// 好汉外号
	public HeroNode next; // 指向下一个节点（好汉）
	// 构造器

	public HeroNode(int no, String name, String nickname) {
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	// 为了显示方法，我们重新toString
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
	}
}
